// 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。
// 假设每一种面额的硬币有无限个。
// 输入: amount = 5, coins = [1, 2, 5]
// 输出: 4
// 解释: 有四种方式可以凑成总金额:
// 5=5
// 5=2+2+1
// 5=2+1+1+1
// 5=1+1+1+1+1
// 求凑成总金额的物品组合个数
function change(amount, coins) {
    let dp = new Array(amount + 1).fill(0)
    dp[0] = 1
    for (let i = 0; i < coins.length; i++) {
        for (let j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]]            
        }        
    }
    return dp[amount]
}

let amount = 5, coins = [1, 2, 5]
console.log(change(amount, coins))

function change2(amount, coins) {
    let dp = new Array(coins.length).fill(0).map(item => new Array(amount + 1).fill(0))
    // 第一列
    for (let i = 0; i < coins.length; i++) {
        dp[i][0] = 1        
    }
    // 第一行
    for (let j = coins[0]; j <= amount; j++) {
        dp[0][j] = dp[0][j - coins[0]]        
    }
    for (let i = 1; i < coins.length; i++) {
        for (let j = 1; j <= amount; j++) {
            if (j < coins[i]) {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]
            }           
        }        
    }
    return dp[coins.length - 1][amount]
}

console.log(change2(amount, coins))